package com.yoso.alg;

import org.junit.jupiter.api.Test;


/**
 * 4.寻找两个正序数组的中位数
 * @author yoso
 * @date 2024-07-20
 */
class Solution4 {
    @Test
    public void test(){
        int[] nums1 = new int[]{};
        int[] nums2 = new int[]{2,3};
        double i = findMedianSortedArrays(nums1, nums2);
        System.out.println("i = " + i);
    }
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 两个数组的大小
        int size = nums1.length + nums2.length;
        // 需要遍历的最小长度，[1,2] --2     [1,2,3] --2 , 无论是奇数个还是偶数个，都需要遍历到size/2 + 1的位置
        int end = size / 2 + 1;
        // 是否是偶数个
        boolean os = size % 2 == 0;
        // 目标中位数（如果是奇数个，该值就是中位数。如果是偶数个，代表目标中位数的较大值）
        int theNum = -1;
        // 目标中位数（如果是偶数个，代表目标中位数的较小值）
        int preNum = -1;
        // 两个数组的指针
        int i = -1;
        int j = -1;
        // 其中一个是空数组，那么俩个引用指向同一个数组
        if (nums1.length == 0) {
            nums1 = nums2;
        }
        if (nums2.length == 0) {
            nums2 = nums1;
        }
        // 找到最小元素，指针移动到起始位置
        // 这里注意，循环还未开始时，指针已经移动了一次了，所以后面的for循环end - 1
        if (nums1[0] <= nums2[0]) {
            i = 0;
            theNum = nums1[0];
        } else {
            j = 0;
            theNum = nums2[0];
        }
        for (int k = 0; k < end - 1; k++) {
            // 如果一个数组遍历完了，遍历另一个
            if (nums1.length == i + 1) {
                nums1 = nums2;
                i = j;
            }
            if (nums2.length == j + 1) {
                nums2 = nums1;
                j = i;
            }
            // 如果两个数组是同一个，指针的滑动是共享的
            if (nums1 == nums2) {
                i = j = Math.max(i, j);
            }
            // 俩个数组滑动到下一个位置的数值
            int nextOne = nums1[i + 1];
            int nextTwo = nums2[j + 1];
            // 记录上一次的数值
            preNum = theNum;
            // 下一个数值小的数组，指针后滑动，并记录数值
            if (nextOne <= nextTwo) {
                theNum = nums1[++i];
            } else {
                theNum = nums2[++j];
            }
        }
        if (os) {
            return (double) (theNum + preNum) / 2;
        }
        return theNum;
    }


}